#include<iostream>
#include<list>
#include<unordered_map>
using std::unordered_map;
using std::endl;
using std::cout;
using std::list;
//重写LRU 




class LRUCache{
public:
    LRUCache(int capacity)
    :_capacity(capacity){}

    int get(int key);
    void put(int key,int value);
private:
struct CacheNode_t
{
    CacheNode_t(int k,int v)
    :key(k)
    ,value(v)
    {}
    int key;
    int value;
};

private:
    int _capacity;
    list<CacheNode_t> _nodes; //主要目的是顺序 
    unordered_map<int,list<CacheNode_t>::iterator> _cache; //只是存数据
};

void LRUCache::put(int key,int value){
    //判断_cache 里面是否有这个数据
    auto it = _cache.find(key);
    if(it != _cache.end()){ //存在的情况
        it->second->value = value;
        //移动到list 顶部
        //splice 自己
        _nodes.splice(_nodes.begin(),_nodes,it->second);
    }
    else{ //if key 不存在
        //判断list是否满了
        if(_nodes.size() == _capacity){
            //删除最后一个
            auto &it = _nodes.back();
            _cache.erase(it.key);
            _nodes.pop_back();

        }
        //插入新的
        _nodes.push_front(CacheNode_t{key,value});
        _cache.insert({key,_nodes.begin()});

    }
}

//查找key
int LRUCache::get(int key){
    auto it = _cache.find(key);
    if(it == _cache.end()){
        //没找到
        return -1;
    }
    else{
        _nodes.splice(_nodes.begin(),_nodes,it->second);
        return it->second->value;
    }
}

int main(void){
    LRUCache lr(2);
    lr.put(1,100);
    cout << "get(1) = " << lr.get(1) << endl;
    lr.put(3, 300);
    cout << "get(2) = " << lr.get(2) << endl;
    lr.put(4, 400);
    cout << "get(1) = " << lr.get(1) << endl;
    cout << "get(3) = " << lr.get(3) << endl;
    cout << "get(4) = " << lr.get(4) << endl;
}